#include <cmath>
#include <iostream>

#include "formula.hpp"
#include "formula_callable.hpp"
#include "gamemap.hpp"
#include "mapgen.hpp"
#include "river.hpp"
#include "terrain.hpp"
#include "tile.hpp"
#include "tile_corner_logic.hpp"
#include "wml_node.hpp"
#include "wml_utils.hpp"

namespace hex {

namespace {

typedef std::vector<std::vector<int> > height_map;

bool river_terminates(const height_map& heights, const gamemap& m, const corner_location& corner)
{
	location adj[3];
	get_adjacent_hexes_to_corner(corner, adj);
	for(int n = 0; n != 3; ++n) {
		if(!m.is_loc_on_map(adj[n]) || m.get_tile(adj[n])->terrain()->is_water()) {
			return true;
		}
	}

	return false;
}

corner_location river_flow(const height_map& heights, const gamemap& m, const corner_location& corner)
{
	int min_height = -1;
	corner_location lowest;
	corner_location adj[3];
	get_adjacent_corners(corner, adj);
	for(int n = 0; n != 3; ++n) {
		location tiles[3];
		get_adjacent_hexes_to_corner(adj[n], tiles);
		int height = 0;
		for(int i = 0; i != 3; ++i) {
			if(m.is_loc_on_map(tiles[i])) {
				height += heights[tiles[i].x()][tiles[i].y()];
			}
		}

		if(lowest.hex.valid() == false || height < min_height) {
			min_height = height;
			lowest = adj[n];
		}
	}

	return lowest;
}

void add_river(river_ptr river, const height_map& heights, gamemap& m, const corner_location& c1, const corner_location& c2)
{
	location adj1[3];
	location adj2[3];
	
	std::vector<location> locs;
	get_adjacent_hexes_to_corner(c1, adj1);
	get_adjacent_hexes_to_corner(c2, adj2);
	for(int i = 0; i != 3; ++i) {
		for(int j = 0; j != 3; ++j) {
			if(adj1[i] == adj2[j]) {
				locs.push_back(adj1[i]);
			}
		}
	}

	assert(locs.size() == 2);

	DIRECTION dir1 = get_adjacent_direction(locs[0], locs[1]);
	DIRECTION dir2 = get_adjacent_direction(locs[1], locs[0]);
	assert(dir1 != NULL_DIRECTION);
	assert(dir2 != NULL_DIRECTION);

	tile_ptr t1 = m.get_tile(locs[0]);
	tile_ptr t2 = m.get_tile(locs[1]);

	t1->add_river(dir1, river);
	t2->add_river(dir2, river);
}

//! Generate a height-map.
//! Basically we generate alot of hills,
//! each hill being centered at a certain point,
//! with a certain radius - being a half sphere.
//! Hills are combined additively to form a bumpy surface.
//! The size of each hill varies randomly from 1-hill_size.
//! We generate 'iterations' hills in total.
//! The range of heights is normalized to 0-1000.
//! 'island_size' controls whether or not the map should tend toward an island shape,
//! and if so, how large the island should be.
//! Hills with centers that are more than 'island_size' away from
//! the center of the map will be inverted (i.e. be valleys).
//! 'island_size' as 0 indicates no island.
static height_map generate_height_map(size_t width, size_t height,
                               size_t iterations, size_t hill_size,
							   size_t island_size, size_t island_off_center)
{
	height_map res(width,std::vector<int>(height,0));

	size_t center_x = width/2;
	size_t center_y = height/2;

	if(island_off_center != 0) {
		switch(rand()%4) {
		case 0:
			center_x += island_off_center;
			break;
		case 1:
			center_y += island_off_center;
			break;
		case 2:
			if(center_x < island_off_center)
				center_x = 0;
			else
				center_x -= island_off_center;
			break;
		case 3:
			if(center_y < island_off_center)
				center_y = 0;
			else
				center_y -= island_off_center;
			break;
		}
	}

	for(size_t i = 0; i != iterations; ++i) {

		// (x1,y1) is the location of the hill,
		// and 'radius' is the radius of the hill.
		// We iterate over all points, (x2,y2).
		// The formula for the amount the height is increased by is:
		// radius - sqrt((x2-x1)^2 + (y2-y1)^2) with negative values ignored.
		//
		// Rather than iterate over every single point, we can reduce the points
		// to a rectangle that contains all the positive values for this formula --
		// the rectangle is given by min_x,max_x,min_y,max_y.

		// Is this a negative hill? (i.e. a valley)
		bool is_valley = false;

		int x1 = island_size > 0 ? center_x - island_size + (rand()%(island_size*2)) :
			                                 int(rand()%width);
		int y1 = island_size > 0 ? center_y - island_size + (rand()%(island_size*2)) :
			                                 int(rand()%height);

		// We have to check whether this is actually a valley
		if(island_size != 0) {
			const size_t diffx = abs(x1 - int(center_x));
			const size_t diffy = abs(y1 - int(center_y));
			const size_t dist = size_t(std::sqrt(double(diffx*diffx + diffy*diffy)));
			is_valley = dist > island_size;
		}

		const int radius = rand()%hill_size + 1;

		const int min_x = x1 - radius > 0 ? x1 - radius : 0;
		const int max_x = x1 + radius < static_cast<long>(res.size()) ? x1 + radius : res.size();
		const int min_y = y1 - radius > 0 ? y1 - radius : 0;
		const int max_y = y1 + radius < static_cast<long>(res.front().size()) ? y1 + radius : res.front().size();

		for(int x2 = min_x; x2 < max_x; ++x2) {
			for(int y2 = min_y; y2 < max_y; ++y2) {
				const int xdiff = (x2-x1);
				const int ydiff = (y2-y1);

				const int height = radius - int(std::sqrt(double(xdiff*xdiff + ydiff*ydiff)));

				if(height > 0) {
					if(is_valley) {
						if(height > res[x2][y2]) {
							res[x2][y2] = 0;
						} else {
							res[x2][y2] -= height;
						}
					} else {
						res[x2][y2] += height;
					}
				}
			}
		}
	}

	// Find the highest and lowest points on the map for normalization:
	int heighest = 0, lowest = 100000, x;
	for(x = 0; size_t(x) != res.size(); ++x) {
		for(int y = 0; size_t(y) != res[x].size(); ++y) {
			if(res[x][y] > heighest)
				heighest = res[x][y];

			if(res[x][y] < lowest)
				lowest = res[x][y];
		}
	}

	// Normalize the heights to the range 0-1000:
	heighest -= lowest;
	for(x = 0; size_t(x) != res.size(); ++x) {
		for(int y = 0; size_t(y) != res[x].size(); ++y) {
			res[x][y] -= lowest;
			res[x][y] *= 1000;
			if(heighest != 0)
				res[x][y] /= heighest;
		}
	}

	return res;
}

class tile_settings_callable : public game_logic::formula_callable
{
public:
	tile_settings_callable(int temperature, int height, int rainfall)
	  : temperature_(temperature), height_(height), rainfall_(rainfall)
	{}
	variant get_value(const std::string& key) const {
		if(key == "height") {
			return variant(height_);
		} else if(key == "temperature") {
			return variant(temperature_);
		} else if(key == "rainfall") {
			return variant(rainfall_);
		} else {
			return variant();
		}
	}

	void get_inputs(std::vector<std::string>* attr) {
		return;
	}
private:
	int temperature_, height_, rainfall_;
};

}

gamemap generate_gamemap(wml::const_node_ptr settings)
{
	const int width = wml::get_int(settings, "width");
	const int height = wml::get_int(settings, "height");
	
	height_map heights = generate_height_map(width, height,
	                            wml::get_int(settings, "height_iterations"),
	                            wml::get_int(settings, "height_hill_size"),
								0, 0);
	height_map temperatures = generate_height_map(width, height,
	                            wml::get_int(settings, "temperature_iterations"),
	                            wml::get_int(settings, "temperature_hill_size"),
								0, 0);
	height_map rainfall = generate_height_map(width, height,
	                            wml::get_int(settings, "rainfall_iterations"),
	                            wml::get_int(settings, "rainfall_hill_size"),
								0, 0);
	const int river_source_min_height = wml::get_int(settings, "river_source_min_height");
	const int river_source_chance = wml::get_int(settings, "river_source_chance");

	std::vector<location> river_sources;

	std::vector<tile_ptr> tiles;
	game_logic::formula tile_formula(settings->attr("tile_formula"));
	for(int y = 0; y != height; ++y) {
		for(int x = 0; x != width; ++x) {
			tile_settings_callable callable(temperatures[x][x], heights[x][y], rainfall[x][y]);
			std::string terrain_type = tile_formula.execute(callable).as_string();
			location loc(x, y);
			tiles.push_back(tile_ptr(new tile(loc, terrain_type)));

			hex::const_terrain_ptr terrain = tiles.back()->terrain();
			const hex::terrain::resource_map& resources = terrain->resources();
			for(hex::terrain::resource_map::const_iterator i = resources.begin(); i != resources.end(); ++i) {
				if(!i->second) {
					continue;
				}
				const int quality = i->second->execute(callable).as_int();
				tiles.back()->add_resource(i->first, quality);
			}

			std::pair<std::string,int> bonus_resource = terrain->generate_bonus_resource();
			if(bonus_resource.second > 0) {
				tiles.back()->add_resource(bonus_resource.first, bonus_resource.second);
			}

			if(heights[x][y] > river_source_min_height && (rand()%1000) < river_source_chance) {
				river_sources.push_back(loc);
			}
		}
	}

	gamemap map(tiles, width, height);

	foreach(const location& source, river_sources) {
		corner_location loc;
		loc.hex = source;
		loc.left_side = (rand()%2) == 0;
		std::vector<corner_location> river_locs;
		river_locs.push_back(loc);
		while(river_locs.size() != 100 && !river_terminates(heights, map, river_locs.back())) {
			river_locs.push_back(river_flow(heights, map, river_locs.back()));
		}

		if(river_locs.size() < 100) {
			std::cerr << "MADE RIVER: " << river_locs.size() << "\n";
			river_ptr r(new river(river_locs));
			map.add_river(r);
			for(int n = 0; n != river_locs.size() - 1; ++n) {
				add_river(r, heights, map, river_locs[n], river_locs[n+1]);
			}
		}
	}

	map.init_heightmap();

	return map;
}
}
